Computer systems are increasingly incorporating multiprocessing architectures which execute parallel software applications that share access to common data structures. Concurrent queues are used in multiprocessing computing environments. To insure "correctness," concurrent access to shared queues is synchronized. Traditional approaches to synchronizing access to critical regions have incorporated preemptive based spinlocks. These approaches are "blocking" and are not suitable for providing multiprocessor safe synchronization of critical regions between multiple threads of execution in user space (i.e. application software). The blocking characteristic of spinlock methods also reduces software scalability in situations of high contention in critical regions of a multiprocessor environment.
A set of concurrent non-blocking methods which demonstrate superior performance over traditional spinlock methods of multiprocessor synchronization have been developed by Maged M. Michael and Michael L. Scott. These methods allow multiple processors to gain concurrent non-blocking access to shared First In First Out (FIFO) queues with immunity from inopportune preemption and are especially useful for parallel software applications requiring shared access to FIFO queues. Furthermore, these methods demonstrate nearly linear scalability under high contention of critical regions in a multiprocessor environment and are incorporated directly in application software. These methods do not affect processor interrupts and do not require spinlock methods to provide mutual exclusion to a shared critical region. These methods are presented and described in greater detail in a publication authored by Maged M. Michael and Michael L. Scott, entitled "Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms," published in the 15th ACM Symposium on Principles of Distributed Computing (PODC), May 1996.
Following is pseudo-code for implementing these methods as presented in the publication:
structure pointer_t {ptr: pointer to node_t, count: undersigned integer} structure node_t {value: data type, next pointer_t} structure queue_t {Head: pointer_t, Tail: pointer_t} initialize(Q: pointer to queue_t) node=new_node() # Allocate a free node node-&gt;next.ptr=NULL # Make it the only node in the linked list Q-&gt;Head=Q-&gt;Tail=node # Both Head and Tail point to it enqueue(Q:pointer to queue_t, value: data type) E1: node=new_node() # Allocate a new node from the free list E2: node-&gt;value=value # Copy equenced value into node E3: node-&gt;next.ptr=NULL # Set next pointer of node to NULL E4: loop # Keep trying until Enqueue is done E5: tail=Q-&gt;Tail # Read Tail.ptr and Tail.count together E6: next=tail.ptr-&gt;next # Read next ptr and count fields together E7: if tail ==Q-&gt;Tail # Are tail and next consistent? E8: if next.ptr==NULL # Was Tail pointing to the last node? E9: if CAS(&tai1.ptr-&gt;next, next, &lt;node, next.count+1&gt;)# Try to link node at the end of the linked list E10: break # Enqueue is done. Exit loop E11: endif E12: else # Tail was not pointing to the last node E13: CAS(&Q-&gt;Tail, tail, &lt;next.ptr, tail.count+1&gt;) # Try to swing Tail to the next node E14: endif E15: endif E16: endloop E17: CAS(&Q-&gt;Tail, tail, &lt;node, tail.count+1) # Enqueue is done. Try to swing to the inserted node dequeue(Q: pointer to queue_t, pvalue: pointer to data type): boolean D1: loop # Keep trying until Dequeue is done D2: head=Q-&gt;Head # Read Head D3: tail=Q-&gt;Tail # Read Tail D4: next=head-&gt;next # Read Head.ptr-&gt;next D5: if head == Q-&gt;Head # Are head, tail, and next consistent? D6: if head.ptr==tail.ptr # Is queue empty or Tail falling behind? D7: if next.ptr==NULL # Is queue empty? D8: return FALSE # Queue is empty, couldn't dequeue D9: endif D10: CAS(&Q-&gt;Tail, tail, &lt;next.ptr, tail.count+1&gt;) # Tail is falling behind. Try to advance it D11: else # No need to deal with Tail # Read value before CAS, otherwise another dequeue might free the next node D12: *pvalue=next.ptr-&gt;value D13: if CAS(&Q-&gt;Head, head, &lt;next.ptr, head.count+1&gt;) # Try to swing Head to the next node D14: break # Dequeue is done. Exit loop D15: endif D16: endif D17: endif D18: endloop D19: free(head.ptr) # It is safe now to free the old dummy node D20: return TRUE # Queue was not empty, dequeue succeeded
One shortcomings of these queuing methods, however, involves a condition referred to as an "ABA" condition. The "ABA" condition occurs on computing platforms, such as the Intel 486 and the Pentium class lines of processors, which utilize a Compare-And-Swap (CAS) atomic primitive. The "ABA" condition occurs when a process reads a value "A" from a shared memory location, computes a new value and then attempts the CAS operation. In certain circumstances, the CAS operation may succeed when it should have failed. Such a situation arises when, between the memory read and the CAS operation, some other process or processes change the value "A" to value "B" and then back to value "A." Although the CAS operation succeeds since the value of the shared memory location has returned to value "A," the value in the memory location to which "A" points may have changed. To reduce the probability of encountering the "ABA" condition, the aforementioned queuing methods implement a sequence or count number as part of node address associated with the shared memory location. The count number is incremented with every successful CAS operation so that a determination can be made as to whether the contents of the shared memory location has been altered. While the use of count numbers reduces the probability of encountering the "ABA" condition, the method falls short on the previously mentioned Intel processors due to the frequent incrementing of the count number which causes the count to wrap around and possibly end up at the original count number. The probability of a wrap around condition occurring is especially likely in high contention situations and increases as the speed of the processor increases and the total number of nodes in the queue decreases.
It would be advantageous therefore, to devise a method and apparatus which selectively increments count numbers associated with nodes in a queue to reduce the number of times the count numbers are incremented. Such a method and apparatus would increase the time between the occurrence of wrap around conditions and thereby, reduce the likelihood of encountering an "ABA" condition.